package likou.bingchaji;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/16 19:47
 */
//684. 冗余连接
public class _684 {
    static class BCJ {
        BCJ bcj;

        BCJ() {
            this.bcj = this;
        }

        BCJ find() {
            if (bcj.bcj != bcj) {
                bcj = bcj.find();
            }
            return bcj;
        }

        void union(BCJ bcj) {
            this.find().bcj = bcj;
        }
    }

    private static int[] result = new int[2];//合并两个连通分量时，赋值答案

    public static int[] findRedundantConnection(int[][] edges) {
        //并查集
        BCJ[] unions = new BCJ[edges.length + 1];
        for (int[] edge : edges) {
            int front = edge[0], next = edge[1];
            BCJ b1 = unions[front], b2 = unions[next];
            if (b1 == null && b2 == null) {
                BCJ b = new BCJ();
                unions[front] = b;
                unions[next] = b;
            } else if (b1 == null) {
                b1 = new BCJ();
                b1.union(b2);
                unions[front] = b1;
            } else if (b2 == null) {
                b2 = new BCJ();
                b2.union(b1);
                unions[next] = b2;
            } else {
                if (b1.find() != b2.find()) {
                    b1.union(b2);
                }else {
                    result = edge;
                }
            }
        }
        return result;
    }
}
